package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * 
 * 
 * @author 付大石
 */
public class MaxPQ {

    public static void main(String[] args) {

        Point p1 = new Point(4, 2, 4);
        Point p2 = new Point(5, 3, 1);
        Point p3 = new Point(3, 2, 4);
        Point p4 = new Point(5, 6, 7);
        Point p5 = new Point(0, 0, 0);
        Point p6 = new Point(2, 3, 4);
        Point p7 = new Point(4, 5, 7);
        Point p8 = new Point(3, 8, 6);
        Point p9 = new Point(2, 3, 5);
        Point p10 = new Point(4, 3, 5);
        MaxPQ pq = new MaxPQ();
        pq.filter(p1);
        pq.filter(p2);
        pq.filter(p3);
        pq.filter(p4);
        pq.filter(p5);
        pq.filter(p6);
        pq.filter(p7);
        pq.filter(p8);
        pq.filter(p9);
        pq.filter(p10);
        System.out.println(pq);
    }

    /**
     * 优先队列容量为5
     */
    private static final int CAPACITY = 5;

    /**
     * 优先队列，元素是{@code Point}的对象实例
     */
    private Point[] pointPQ;

    /**
     * 优先队列内元素个数
     */
    private int size;

    public MaxPQ() {
        pointPQ = new Point[CAPACITY + 1];
    }

    public void filter(Point[] pointArr) {

        for (Point point : pointArr) {
            filter(point);
        }
    }

    public void filter(Point point) {

        System.out.println(point);
        if (size < CAPACITY) {
            pointPQ[++size] = point;
            swim(size);
        } else { // 队列已满，需过滤
            if (pointPQ[1].compareTo(point) > 0) {
                pointPQ[1] = point;
                sink(1);
            }
        }
    }

    public void sink(int k) {

        Point target = pointPQ[k];
        while (2 * k <= size) {
            int i = 2 * k;
            if (i + 1 <= size && pointPQ[i].compareTo(pointPQ[i + 1]) < 0) {
                i++;
            }
            if (target.compareTo(pointPQ[i]) < 0) {
                break;
            }
            pointPQ[k] = pointPQ[i];
            k = i;
        }
        pointPQ[k] = target;
    }

    public void swim(int k) {

        Point target = pointPQ[k];
        while (k > 1 && target.compareTo(pointPQ[k / 2]) > 0) {
            pointPQ[k] = pointPQ[k / 2];
            k = k / 2;
        }
        pointPQ[k] = target;
    }

    @Override
    public String toString() {

        StringBuilder builder = new StringBuilder();
        builder.append("size:").append(size).append("\t").append(Arrays.toString(pointPQ));
        return builder.toString();
    }

}
